package singleLinked;

//shift+f6替换

//顺序表[ArrayList]
//优点：当给定下标的时候，查找速度非常快。适合给定下标的查找。O(1)
//缺点：必须得挪动元素，然后才能插入；必须挪动元素，才能删除；每次扩容也是浪费资源的。


// 1、无头单向非循环链表实现
public class SingleLinkedList {
    //链表的结点
    static class ListNode {
        public int val;//存储的数据
        public ListNode next;//存储下一个节点的地址

        public ListNode(int val) {
            this.val = val;
        }
    }


    public ListNode head;//表示当前链表的头结点

    //===============================================
    //打印链表
    public void display() {
        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //使用递归逆序打印链表
    public void displayRecu(ListNode node) {
        if (node == null) {
            return;
        }
        if (node.next == null) {
            System.out.print(node.val+" ");
            return;
        }
        displayRecu(node.next);
        System.out.print(node.val+" ");
    }


    //===============================================
    //头插法【比较简单，整体也没有特殊情况，head=null也没问题！】
    public void addFirst(int data) {
        ListNode newNode = new ListNode(data);
        newNode.next = head;
        head = newNode;
    }

    //===============================================
    //尾插法【需要考虑头结点为null的情况】
    public void addLast(int data) {
        ListNode newNode = new ListNode(data);
        ListNode cur = head;
        //如果头结点为空，直接赋值
        if (head == null) {
            head = newNode;
            return;
        }
        //找到尾结点
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = newNode;

    }

    //========================================================
    private void checkIndex(int index) {
        if (index < 0 || index > size()) {
            throw new IndexOutOfException("下标越界！");
        }
    }

    /**
     * 找到 index-1位置的节点的地址
     *
     * @param index
     * @return
     */
    private ListNode findIndexSubOne(int index) {
        ListNode cur = head;
        int count = 0;
        while (count != index - 1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index, int data) throws IndexOutOfException {
        //判断坐标合法性【这里判断了坐标的合法性，不会出现head=null，index=3】
        checkIndex(index);

        //index=0这种情况需要特殊处理一下【1.head=null,index=0;2.head!=null,index=0】
        if (index == 0) {
            addFirst(data);
            return true;
        }
        //尾插不用特殊考虑，以下包含了尾插

        //中间插入
        ListNode newNode = new ListNode(data);
        ListNode cur = findIndexSubOne(index);
        newNode.next = cur.next;
        cur.next = newNode;
        return true;
    }
    //===============================================

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //==============================================

    /**
     * 找到关键字key的前一个节点
     *
     * @param key
     * @return
     */
    private ListNode searchPrev(int key) {

        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        //链表一个结点都没有
        if (head == null) {
            System.out.println("链表为空！");
            return;
        }
        //判断头结点的val
        if (head.val == key) {
            head = head.next;
            return;
        }
        //找到key的前驱结点
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                cur.next = cur.next.next;
                return;
            }
            cur = cur.next;
        }
        System.out.println("未找到关键字" + key);
//        ListNode pre = searchPrev(key);
//        if (pre==null) {
//            System.out.println("未找到关键字"+key);
//        } else {
//            pre.next=pre.next.next;
//        }
    }

    //=======================================================
    //删除所有值为key的节点
    public void removeAllKey(int key) {
        //为空情况
        if (head == null) {
            return;
        }
        //除头结点后的情况
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        //头结点单独判断
        if (head.val == key) {
            head = head.next;
        }
    }

    //===============================================
    //得到单链表的长度
    public int size() {
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    //===============================================
    //清空链表
    public void clear() {
        head = null;
    }

}





